package io.gitee.wiqer.medium;

import io.gitee.wiqer.ListNode;

/**
 * 描述
 * 给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。
 * 例如：
 * 给出的链表为1 \to 2\to 3\to 3\to 4\to 4\to51→2→3→3→4→4→5, 返回1\to 2\to51→2→5.
 * 给出的链表为1\to1 \to 1\to 2 \to 31→1→1→2→3, 返回2\to 32→3.
 *
 * 数据范围：链表长度 0 \le n \le 100000≤n≤10000，链表中的值满足 |val| \le 1000∣val∣≤1000
 * 要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)
 * 进阶：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
 */
public class SolutionNC24_DeleteDuplicates {
    /**
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode deleteDuplicates (ListNode head) {
        // write code here
        ListNode cur = head;
        ListNode pre=null;
        while (cur !=null){
            /**
             * cur指针跳到最后一个不与下一个数相等的节点
             */
            boolean tmp = false;
            while (cur.next!=null&&cur.val==cur.next.val) {
                cur=cur.next;
                //记录跳过
                tmp=true;
            }
            if (!tmp) { // 如果以前没有相同的节点，则pre指向当前节点，保证下次遇到相同的节点设置next
                if(pre==null){
                    pre = cur;
                }else {
                    pre.next= cur;
                    pre=pre.next;
                }
            }else {
                cur=cur.next;
            }

        }
        return pre;
    }
}
